Apa itu Dynamic Programming?
Rahasia menyelesaikan masalah kompleks dengan cara "mengingat masa lalu".
👩🏫 Secara Formal:
Dynamic Programming (DP) adalah metode optimasi algoritma untuk memecahkan masalah kompleks dengan memecahnya menjadi sub-masalah yang lebih kecil (seperti rekursi), NAMUN menyimpan hasil perhitungan dari sub-masalah tersebut (Memoization/Tabulation) agar tidak dihitung ulang. DP mensyaratkan 2 hal: Overlapping Subproblems (masalah berulang) dan Optimal Substructure (solusi global didapat dari solusi optimal lokal).
Analogi Jaman Now
Bayangin kamu disuruh ngitung `1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = ?`. Kamu ngitung manual, lalu jawab "8!".
Terus guru nambahin `+ 1` di akhir. Apakah kamu ngitung ulang dari awal lagi `1 + 1 + 1...`?
Nggak kan! Kamu pasti ingat "Oh, yang tadi kan 8, tinggal tambah 1 jadi 9."
Nah, itu dia esensi DP! "Mengingat (menyimpan) masa lalu, supaya ngga capek ngitung ulang."
⚠️ Common Mistakes: Lupa Array Base Case
Kesalahan pemula saat koding DP adalah mendeklarasikan array `memo[N]`, tapi lupa menginisialisasinya (misal lupa diset dengan -1), atau lupa mengisi Base Case (`memo[0] = 0`). Akibatnya, jawaban jadi ngawur karena terisi "garbage value" atau program mengalami rekursi tak hingga!
Pohon Pemanggilan: Fibonacci
Mengapa Rekursi Biasa sangat lambat dan butuh Memoization (Top-Down)?
VISUALISASI REKURSI vs DP (FIBONACCI 5)
Klik tombol di atas untuk membandingkan banyaknya pemanggilan fungsi `F(n)` antara Rekursi Biasa (Brute Force) vs Memoization (DP).
Lab Interaktif: Time Complexity
Pilih nilai N, lalu lihat perbedaan jumlah pemanggilan fungsi.
Tabulation (Bottom-Up)
Membangun jawaban dari bawah (paling kecil) ke atas menggunakan Array.
👩🏫 Secara Formal:
Tabulation (Bottom-Up) adalah pendekatan DP tanpa menggunakan rekursi sama sekali. Kita mendeklarasikan sebuah array `dp[]`, lalu mengisi dari indeks terkecil (Base Case: `dp[0], dp[1]`) dan menggunakan iterasi *for-loop* untuk mengisi nilai-nilai berikutnya `dp[i]` berdasarkan nilai-nilai sebelumnya. Pendekatan ini lebih cepat dan aman dari Stack Overflow.
Visualisasi Tabulation: Fibo(8)
IMPLEMENTASI C++ (BOTTOM-UP)
int dp[100];
dp[0] = 0; // Base case 1
dp[1] = 1; // Base case 2
// Isi tabel dari bawah ke atas menggunakan for-loop
for (int i = 2; i <= N; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
cout << dp[N] << endl;
Studi Kasus: Coin Change
Menemukan jumlah koin paling minimum (Ingat: Greedy bisa gagal di sini!).
Masalah:
Kamu punya koin bernilai [1, 3, 4] dan harus membayar tagihan sebesar 6.
Jika pakai Greedy: Ambil koin terbesar (4) -> sisa 2 -> koin (1) -> koin (1) = 3 koin. (SALAH)
Padahal solusi optimalnya: Pakai koin (3) + koin (3) = 2 koin saja! (DP BENAR)
Lab Interaktif: Coin Change DP Tabel
Koin: [1, 3, 4]. Tagihan = 6. Cari `dp[i]` = Minimum koin untuk nilai `i`.
Siap untuk Ujian OSN?
Selesaikan kuis format soal OSN-K mengenai Dynamic Programming Dasar.
Mulai Kuis Minggu 11